import java.util.Scanner;

public class Test {
    /*这个是模式匹配算法*/
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Test test=new Test();
        System.out.println("请输入文本串");
        while (in.hasNext()){

            String s1=in.nextLine();
            System.out.println("请输入查找串");
            String s2=in.nextLine();
            int ret= test.Sunday(s1,s2);
            if (ret != -1){
                System.out.println("查找成功,第一次出现的下标为"+ret);
            }else {
                System.out.println("匹配失败");
            }


        }

    }
    public int Sunday(String textSting, String matchSting) {
        int hayLen = textSting.length();
        int nLen = matchSting.length();

        int i = 0;//haystack串的游标索引
        int j = 0;// needle串的游标索引


        while (i <= hayLen - nLen) {
            // textSting剩余字符少于matchSting串时跳过比较,说明没有匹配成功的

            while (j < nLen && textSting.charAt(i + j) == matchSting.charAt(j)) {
                // 将文本串串与模式串串中参与比较的子串进行逐个字符比对
                j++;
            }

            // 如果j等于模式串的长度说明此时匹配成功，可以直接返回此时主串的下标索引
            if (j == nLen) {
                return i;
            }

            // 不匹配时计算需要跳过的字符数，移动主串游标i
            if (i < hayLen - nLen) {
                // 对照字符在模式串存在，则需要跳过的字符数为从对照字符在模式串中最后出现的位置起剩余的字符个数
                // 不存在则跳过的字符数为模式串长度+1，也就是代码nLen-(-1)的情况
                i += (nLen - lastIndex(matchSting, textSting.charAt(i + nLen)));
            } else {
                return -1;
            }
            // 每次比较之后将needle游标置为0
            j=0;
        }

        return -1;
    }

    public int lastIndex(String str, char ch) {
        // 从后往前检索
        for (int j = str.length() - 1; j >= 0; j--) {
            if (str.charAt(j) == ch) {
                return j;
            }
        }
        return -1;
    }
}
